package com.github.hgkmail.hello.leetcode101.design;

import java.util.HashMap;
import java.util.Map;
import java.util.TreeSet;

public class LC460LFUCache {
    //O(logN)的解答
    public static class LFUCache1 {
        class LFUNode implements Comparable<LFUNode> {
            int key;
            int value;
            int count; //次数、频数（越小则使用频率越低）
            int time; //时间（越小则越久未使用）

            public LFUNode() {}
            public LFUNode(int k, int v, int c, int t) {
                key=k;
                value=v;
                count=c;
                time = t;
            }

            //重写compareTo、equals、hashCode方法
            @Override
            public int compareTo(LFUNode o) {
                //先比较count，再比较time
                return count!=o.count ? count-o.count : time-o.time;
            }

            @Override
            public boolean equals(Object o) {
                if (this == o) return true;
                if (o == null || getClass() != o.getClass()) return false;
                LFUNode node = (LFUNode) o;
                return count == node.count && time == node.time; //count和time都相等时，才优先级相同
            }

            @Override
            public int hashCode() {
                return count*10000007+time; //尽量提高count的优先级
            }
        }

        private final int capacity;
        private int time; //用于生成时间
        private final Map<Integer, LFUNode> find;
        private final TreeSet<LFUNode> treeSet;

        public LFUCache1(int cap) {
            capacity = cap;
            time=0;
            find = new HashMap<>();
            treeSet = new TreeSet<>();
        }

        public int get(int key) {
            if (!find.containsKey(key)) {
                return -1;
            }
            //时间+1
            time+=1;
            LFUNode node = find.get(key);
            //更新count和time，重新插入到tree set和hashmap（hashmap也要重新插入，因为重写了hashCode方法）
            treeSet.remove(node);
            node.count+=1;
            node.time=time;
            treeSet.add(node);
            find.put(key, node);

            return node.value;
        }

        public void put(int key, int value) {
            time+=1;
            if (find.containsKey(key)) {
                //这里与get类似
                LFUNode existNode = find.get(key);
                treeSet.remove(existNode);
                existNode.count+=1;
                existNode.time=time;
                existNode.value=value;
                treeSet.add(existNode);
                find.put(key, existNode);
                return;
            }
            //易错点：这里要先判断是否溢出，再插入新元素，否则新元素永远是频数最小的，插不进去
            if (find.size() >= capacity) {
                //淘汰最小的节点first()
                LFUNode leastNode = treeSet.first();
                find.remove(leastNode.key);
                treeSet.remove(leastNode);
            }
            LFUNode freshNode = new LFUNode(key, value, 1, time);
            find.put(key, freshNode);
            treeSet.add(freshNode);
        }
    }

    //O(1)的解答 todo
    class LFUCache2 {

        public LFUCache2(int capacity) {
            //todo
        }

        public int get(int key) {
            return 0;
        }

        public void put(int key, int value) {

        }
    }

    public static void main(String[] args) {
        LFUCache1 lfu = new LFUCache1(2);
        lfu.put(1, 1);   // cache=[1,_], cnt(1)=1
        lfu.put(2, 2);   // cache=[2,1], cnt(2)=1, cnt(1)=1
        lfu.get(1);      // 返回 1
        lfu.put(3, 3);   // 去除键 2 ，因为 cnt(2)=1 ，使用计数最小
        lfu.get(2);      // 返回 -1（未找到）
        lfu.get(3);      // 返回 3
        lfu.put(4, 4);   // 去除键 1 ，1 和 3 的 cnt 相同，但 1 最久未使用
        lfu.get(1);      // 返回 -1（未找到）
        lfu.get(3);      // 返回 3
        lfu.get(4);      // 返回 4

    }
}
